class Solution:
	# @param {integer[]} nums
	# @return {integer}
	def maxSubArray(self, nums):
		m = [None for i in nums]
		ans = m[0] = nums[0]
		for i in xrange(1,len(nums)):
			m[i] = max(m[i-1]+nums[i], nums[i])
			ans = max(m[i], ans)
		return ans

if __name__ == '__main__':
	a = [-2,1,-3,4,-1,2,1,-5,4]
	so = Solution()
	print so.maxSubArray(a)